Error correction techniques and architectures are well known in digital data processing and communications systems, including systems having data storage subsystems such as magnetic, optical, or semiconductor based memory stores.
Detection and, where possible, correction of erroneous data has been achieved by using an encoder circuit to construct some number of “redundant” m-bit error check symbol, which mathematically characterize the information in a selected block of data. The error check symbol is then appended to the data block and transferred through a communication channel. When the data block is received, or later retrieved from memory, the accuracy or reliability of the data can be evaluated by use of these appended error check symbol.
Cyclic Redundancy check (CRC) is a classical error detection mechanism that is widely known in the art and used in numerous applications as a means to detect errors from a transmitted stream of information. Its general acceptance is due to the simplicity of implementation by which it can be used to encode into a stream of information to be transmitted and subsequently checked at the receiver.
CRC calculation is performed in polynomial arithmetic, whereby the basis of the algorithm is; that given both transmitter and receiver mutually acknowledge the use of the same polynomial generator, which is essentially a sequence of information used to construct and verify the error check symbol (in the context of CRC, it is also known as checksum) from the data stream, a stream of information (also known as packets or frames) is transmitted, whereby calculation of the error check symbol is created by performing polynomial division on the data stream against the chosen polynomial generator.
In prior art, in order to optimize the speed at which the error check symbol can be calculated, some have opted for the solution of deriving Boolean or logical expressions that are valid for specific polynomial generators with fixed data width, while other methodologies optimize the idea of using LFSR (linear feedback shift registers), but instead of single bit shifts, many bits or bytes may be shifted per clock cycle, however this then imposes additional rules for the algorithm. Further still, some methodologies proposed by the prior art attempts to optimize operation of performing CRC by checking for unchanged parts of certain streams of information, while others attempt to improve methodology by calculating partial remainders based on segments of the packet of information.